package leetcode.year2021.month11;

// 338. 比特位计数
public class _17_1CountBits338 {
  public int[] countBitsDp(int n) {
    int[] bits = new int[n + 1];
    int highBit = 0;
    for (int i = 1; i <= n; i++) {
      if ((i & (i - 1)) == 0) {
        highBit = i;
      }
      bits[i] = bits[i - highBit] + 1;
    }
    return bits;
  }

  // 三种方式，使用Integer基础库
  public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i < n + 1; i++) {
//      ans[i] = Integer.bitCount(i);
      ans[i] = getBitsByNum1(i);
    }
    return ans;
  }

  private int getBitsByNum1(int i) {
    int ans = 0;
    while (i != 0){
      if (i % 2 == 1){
        ans++;
      }
      i = i >> 1;
    }
    return ans;
  }

  private int getBitsByNum(int i) {
    int res = 0;
    while (i != 0){
      if (i % 2 == 1){
        res++;
      }
      i = i/2;
    }
    return res;
  }


  /**
   * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：n = 2
   * 输出：[0,1,1]
   * 解释：
   * 0 --> 0
   * 1 --> 1
   * 2 --> 10
   * 示例 2：
   *
   * 输入：n = 5
   * 输出：[0,1,1,2,1,2]
   * 解释：
   * 0 --> 0
   * 1 --> 1
   * 2 --> 10
   * 3 --> 11
   * 4 --> 100
   * 5 --> 101
   *  
   *
   * 提示：
   *
   * 0 <= n <= 105
   *  
   *
   * 进阶：
   *
   * 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
   * 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/counting-bits
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
